/*
 * @lc app=leetcode.cn id=54 lang=java
 *
 * [54] 螺旋矩阵
 *
 * https://leetcode-cn.com/problems/spiral-matrix/description/
 *
 * algorithms
 * Medium (37.86%)
 * Likes:    266
 * Dislikes: 0
 * Total Accepted:    35.7K
 * Total Submissions: 93.7K
 * Testcase Example:  '[[1,2,3],[4,5,6],[7,8,9]]'
 *
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 *
 * 示例 1:
 *
 * 输入:
 * [
 * ⁠[ 1, 2, 3 ],
 * ⁠[ 4, 5, 6 ],
 * ⁠[ 7, 8, 9 ]
 * ]
 * 输出: [1,2,3,6,9,8,7,4,5]
 *
 *
 * 示例 2:
 *
 * 输入:
 * [
 * ⁠ [1, 2, 3, 4],
 * ⁠ [5, 6, 7, 8],
 * ⁠ [9,10,11,12]
 * ]
 * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
 *
 *
 */

// @lc code=start
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0) {
            return new ArrayList<>();
        }
        int left = 0, up = 0, right = matrix[0].length-1, down = matrix.length-1;
        ArrayList<Integer> list = new ArrayList<>();
        //boolean[][] dp = new boolean[down+1][right+1];
        while(left <= right && up <= down) {
            for(int i = left; i <=right; i++) {
                list.add(matrix[up][i]);
            }
            up++;
            for(int i = up; i <= down; i++) {
                list.add(matrix[i][right]);
            }
            right--;
            if(right < left || down < up) {
                break;
            }
            for(int i = right; i >= left; i--) {
                list.add(matrix[down][i]);
            }
            down--;
            for(int i = down; i >= up; i--) {
                list.add(matrix[i][left]);
            }
            left++;
        }
        return list;
    }
}
// @lc code=end

